/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * 填充二叉树每个节点的下一个右侧节点指针
 * @param {Node} root - 二叉树根节点
 * @return {Node} - 返回填充后的根节点
 */
var connect = function (root) {
  // 处理空树的情况
  if (root === null) {
    return null;
  }

  // 使用队列进行层序遍历（BFS）
  const queue = [root];

  // 遍历每一层
  while (queue.length > 0) {
    const levelSize = queue.length;

    // 处理当前层的每个节点
    for (let i = 0; i < levelSize; i++) {
      const current = queue.shift();

      // 如果不是当前层的最后一个节点，连接到下一个右侧节点
      if (i < levelSize - 1) {
        current.next = queue[0];
      }

      // 将非空左子节点加入队列
      if (current.left !== null) {
        queue.push(current.left);
      }

      // 将非空右子节点加入队列
      if (current.right !== null) {
        queue.push(current.right);
      }
    }
  }

  return root;
};